Preuve de la fidélité du système RSA

Énoncé

Soit \(p\) et \(q\) deux nombres premiers distincts. On note \(N=pq\) et \(n=(p-1)(q-1)\) .
Soit \(c\) un entier tel que \(1 \leqslant c et \(\mathrm{PGCD}(c;n)=1\) .

1. Soit \(a\) un entier naturel premier avec \(p\) et \(q\) .
    a. Démontrer que \(a^{n} \equiv 1 \ [p]\) et \(a^{n} \equiv 1 \ [q]\) .
    b. En déduire que \(a^{n} \equiv 1 \ [N]\) .

2. Démontrer que, pour tout \(a \in \mathbb{N}\) , si \(k\) est un entier qui vérifie \(k \equiv 1 \ [n]\) , alors \(a^k \equiv a \ [N]\) .

3. a. Justifier que l'équation \((E) \colon cx-ny=1\) admet des solutions dans \(\mathbb{Z}^2\) .
    b. Soit \((x_0;y_0)\) une solution particulière de \((E)\) . Prouver que \((x;y)\) est solution de \((E)\) si, et seulement si, \(x=x_0+kn\) et \(y=y_0+kc\) où \(k \in \mathbb{Z}\) .
    c. En déduire qu'il existe un unique entier \(d\) tel que \(1 \leqslant d et \(cd \equiv 1 \ [n]\) .

4. En utilisant les questions précédentes, montrer que, pour tout  \(a\) , \(b \in \mathbb{N}\) , si \(b \equiv a^c \ [N]\) , alors \(b^d \equiv a \ [N]\) .